package logique.calculateur;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;

import logique.reseau.Troncon;
import logique.reseau.Ville;

public class Optimal extends Algorithme{
	
	public Itineraire calcule() {
		Itineraire solution;

		int nbChemins;
		Ville[][] todo;

		int nbEtapes = prefs.getEtapesObligatoires().getEtapes().size();

		// cas particuliers à 0 ou 1 étape intermédiaire

		if (nbEtapes == 0){
			Dijkstra d = new Dijkstra(calculateur);
			return new Itineraire(prefs.getVilleDepart(), d.calculPCC(prefs.getVilleDepart(), prefs.getVilleArrivee(), prefs));
		}

		if (nbEtapes == 1){
			Dijkstra d = new Dijkstra(calculateur);
			ArrayList<Itineraire> its = new ArrayList<Itineraire>();
			its.add(new Itineraire(prefs.getVilleDepart(), d.calculPCC(prefs.getVilleDepart(), prefs.getEtapesObligatoires().getEtapes().getFirst(), prefs)));
			its.add(new Itineraire(prefs.getEtapesObligatoires().getEtapes().getFirst(), d.calculPCC(prefs.getEtapesObligatoires().getEtapes().getFirst(), prefs.getVilleArrivee(), prefs)));
			return new Itineraire(prefs.getVilleDepart(), its);
		}

		// structure permettant de retrouver l'itinéraire calculé par Dijkstra
		// entre deux villes
		HashMap<Ville, HashMap<Ville, Itineraire>> chemins = new HashMap<Ville, HashMap<Ville,Itineraire>>();
		for (Ville v : prefs.getEtapesObligatoires().getEtapes()){
			chemins.put(v, new HashMap<Ville, Itineraire>());
		}
		chemins.put(prefs.getVilleDepart(), new HashMap<Ville, Itineraire>());

		nbChemins = nbEtapes * (nbEtapes-1) / 2;

		todo = new Ville[nbChemins][2];

		int index = 0;

		// création de la liste des chemins à calculer

		for (int i = 0; i < nbEtapes-1; i++){
			for (int j = i+1; j < nbEtapes; j++){

				todo[index][0] = prefs.getEtapesObligatoires().getEtapes().get(i);
				todo[index][1] = prefs.getEtapesObligatoires().getEtapes().get(j);

				index++;

			}
		}

		Dijkstra d = new Dijkstra(calculateur);
		LinkedList<Troncon> troncons;

		// calcul des chemins entre étapes

		for (int i = 0; i < nbChemins; i++){

			troncons = d.calculPCC(todo[i][0], todo[i][1], prefs);

			chemins.get(todo[i][0]).put(todo[i][1], new Itineraire(todo[i][0], new LinkedList<Troncon>(troncons)));
			chemins.get(todo[i][1]).put(todo[i][0], chemins.get(todo[i][0]).get(todo[i][1]).inverse());
		}

		// calcul des chemins entre les extrémités et les étapes
		for (Ville v : prefs.getEtapesObligatoires().getEtapes()){

			// début - étape
			troncons = d.calculPCC(prefs.getVilleDepart(), v, prefs);
			chemins.get(prefs.getVilleDepart()).put(v, new Itineraire(prefs.getVilleDepart(), new LinkedList<Troncon>(troncons)));

			// étape - fin
			troncons = d.calculPCC(v, prefs.getVilleArrivee(), prefs);
			chemins.get(v).put(prefs.getVilleArrivee(), new Itineraire(v, new LinkedList<Troncon>(troncons)));
		}

		solution = meilleurItineraire(chemins);
		return solution;

	}

	/**
	 *  On teste toutes les combinaisons de chemins possibles. 
	 *  (n)! combinaisons avec n le nombre d'étapes intermédiaires
	 */
	private Itineraire meilleurItineraire(HashMap<Ville, HashMap<Ville, Itineraire>> chemins){

		LinkedList<Ville> etapes = prefs.getEtapesObligatoires().getEtapes();
		int nbEtapes = etapes.size();

		int fact = factorielle(nbEtapes);

		int indiceEtapes;
		int indice;

		Ville villePrecedente;
		Ville villeCourante;

		ArrayList<Ville> visites = new ArrayList<Ville>(nbEtapes);

		int meilleurScore = Integer.MAX_VALUE;

		ArrayList<Itineraire> itineraireCourant = new ArrayList<Itineraire>();
		ArrayList<Itineraire> meilleur = new ArrayList<Itineraire>();
		int scoreCourant = 0;

		// indique s'il est inutile de continuer à évaluer un chemin
		boolean inutile = false;

		// les (n-2)! cas
		for (int i = 0; i < fact; i++){

			itineraireCourant.clear();

			villePrecedente = prefs.getVilleDepart();

			// nombre de choix pour un chemin
			for (int j = 0; j < nbEtapes && !inutile; j++){

				indiceEtapes = (int)Math.floor( (1.0*i / factorielle(nbEtapes-j) * (nbEtapes-j)) % (nbEtapes-j) );

				// on parcourt l'ensemble des possibilités
				// en ne tenant pas compte de celles déjà  visitées

				indice = 0;

				for (int k = 0; k < nbEtapes && indiceEtapes >= 0 ; k++){

					if (!visites.contains(etapes.get(k)))
						indiceEtapes --;

					if (indiceEtapes >= 0)
						indice++;

				}

				if (indice >= nbEtapes)
					indice--;

				villeCourante = etapes.get(indice);

				// on ajoute l'itinéraire choisi à la liste et on met à jour le poids

				itineraireCourant.add(chemins.get(villePrecedente).get(villeCourante));
				scoreCourant += chemins.get(villePrecedente).get(villeCourante).getScore();

				// si on a dépassé le meilleur on arrete d'évaluer ce chemin
				inutile = scoreCourant >= meilleurScore;
				
				// et éventuellement on zappe toutes les possibilités passant par ce début de chemin
				// dernier niveau : rien à faire
				if (inutile && j < nbEtapes-1){
					i += factorielle(nbEtapes - j - 1) - 1;
				}

				villePrecedente = villeCourante;
				visites.add(etapes.get(indice));

			}

			if (!inutile){

				itineraireCourant.add(chemins.get(villePrecedente).get(prefs.getVilleArrivee()));
				scoreCourant += chemins.get(villePrecedente).get(prefs.getVilleArrivee()).getScore();
			}

			inutile = scoreCourant >= meilleurScore;

			if (!inutile){

				meilleurScore = scoreCourant;
				meilleur = new ArrayList<Itineraire>(itineraireCourant);

			}

			scoreCourant = 0;

			inutile = false;
			visites.clear();

		}


		return new Itineraire(prefs.getVilleDepart(), meilleur);

	}



	/* (non-Javadoc)
	 * @see logique.calculateur.Algorithme#getInitialisation()
	 */
	@Override
	public Initialisation getInitialisation() {
		// TODO Auto-generated method stub
		return null;
	}

	public static int factorielle(int nb){
		int fact = 1;
		for (int i = 1; i <= nb; i++)
			fact *= i;

		return fact;
	}

}
